package lib

import(
	"algorithms/ds"
	"strings"
	"strconv"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         297,
		Discription: "二叉树的序列化和反序列化",
		Level:       3,
		Labels: map[string]int{
			"二叉树": 1,
			"层次遍历":  1,
		},
	})
}

type Codec struct {
}

func Constructor6() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
// 在层次遍历的过程中，把空节点当正常的节点记录
// 包括nil在内的层次遍历记录（nil的孩子不记录，也就意味碰到nil，nil需要进值队列，但其孩子不进遍历用到q队列）
func (c *Codec) Serialize(root *ds.TreeNode) string {
	if root == nil {
		return ""
	}

	var builder strings.Builder
	q := []*ds.TreeNode{root}
	for len(q) > 0 {
		node := q[0]
		q = q[1:]

		if node == nil {
			builder.WriteString(",nil")
			continue
		}

		builder.WriteString(",")
		builder.WriteString(strconv.Itoa(node.Val))
		q = append(q, node.Left)
		q = append(q, node.Right)
	}

	res := builder.String()
	return res[1:]
}

// Deserializes your encoded data to tree.
// 按层次遍历的顺序构建节点,先确定节点的值，再进队，等待出队的时候确认左右孩子
func (c *Codec) Deserialize(data string) *ds.TreeNode {
	if data == "" {
		return nil
	}

	vals := strings.Split(data, ",")
	rootVal, _ := strconv.Atoi(vals[0])
	root := &ds.TreeNode{
		Val: rootVal,
	}
	//q代表待处理节点的队列（值确定，孩子未确定）
	q := []*ds.TreeNode{root}
	i := 1

	for len(q) != 0 {
		node := q[0]
		q = q[1:]

		if vals[i] != "nil" {
			leftVal, _ := strconv.Atoi(vals[i])
			left := &ds.TreeNode{
				Val: leftVal,
			}
			node.Left = left
			q = append(q, left)
		}

		if vals[i+1] != "nil" {
			rightVal, _ := strconv.Atoi(vals[i+1])
			right := &ds.TreeNode{
				Val: rightVal,
			}
			node.Right = right
			q = append(q, right)
		}

		i += 2

	}

	return root
}
